public class 链表中环的入口结点 {
    
    public static void main(String[] args) {
        
        // 创建有环链表：1->2->3->4->2（2 节点形成环）
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;

        ListNode entryNode = EntryNodeOfLoop(node1);
        if (entryNode!= null) {
            System.out.println("环的入口结点值为：" + entryNode.val);
        } else {
            System.out.println("链表中无环");
        }

    }

    private static ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        ListNode slow = pHead;
        ListNode fast = pHead;
        boolean hasCycle = false;
        while (fast!= null && fast.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle) {
            return null;
        }
        slow = pHead;
        while (slow!= fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
